import java.util.Arrays;
import java.util.List;

/**
 * Created with Intellij IDEA.
 * Description:
 * User: 28318
 * Date: 2025-11-01
 * Time: 13:04
 */

public class Main {

    public static void main(String[] args) {
        int[][] nums = {
                {1,2,3,0,0,0},
                {2,5,6},
                {1},
                {},
                {0},
                {1}
        };
        for (int i = 0; i < nums.length - 1; i += 2) {
            merge(nums[i], nums[i].length - nums[i + 1].length, nums[i + 1], nums[i + 1].length);
            System.out.println(Arrays.toString(nums[i]));
            System.out.println(Arrays.toString(nums[i + 1]));
        }

    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] newNum = new int[m];
        for (int i = 0; i < m; i++) {
            newNum[i] = nums1[i];
        }
        for (int i = 0, j = 0, k = 0; k < m + n && m != 0 && n != 0; k++) {
            if (i == -1){
                nums1[k] = nums2[j];
                if (j < n - 1){
                    j++;
                } else if (j == n - 1) {
                    j = -1;
                }
            } else if (j == -1) {
                nums1[k] = newNum[i];
                if (i < m - 1){
                    i++;
                } else if (i == m - 1) {
                    i = -1;
                }
            } else if (newNum[i] >= nums2[j]){
                nums1[k] = nums2[j];
                if (j < n - 1){
                    j++;
                } else if (j == n - 1) {
                    j = -1;
                }
            } else if (newNum[i] < nums2[j]){
                nums1[k] = newNum[i];
                if (i < m - 1){
                    i++;
                } else if (i == m - 1) {
                    i = -1;
                }
            }
        }
        if (m == 0){
            for (int i = 0; i < m + n; i++) {
                nums1[i] = nums2[i];
            }
        }
    }

    public static void main8(String[] args) {
        int[][] nums = {
                {1,2,3,4,5,6,7},
                {-1,-100,3,99}
        };
        rotate(nums[0],3);
        rotate(nums[1],2);
        for (int[] num : nums) {
            System.out.println(Arrays.toString(num));
        }
    }

    public static void rotate(int[] nums, int k) {
        /*
        for (int i = 0; i < k; i++) {
            int temp = nums[nums.length - 1];
            for (int j = nums.length - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = temp;
        }
        */
        int[] newNum = new int[nums.length + k];
        for (int i = 0; i < nums.length; i++) {
            newNum[i + k] = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            if (i < k){
                nums[i] = newNum[i + (k / nums.length) * nums.length + k % nums.length];
            }else {

            }
        }
    }

    public static void main7(String[] args) {
        int[][] nums = {
                {3,0,1},
                {9,6,4,2,3,5,7,0,1}
        };
        System.out.println(missingNumber(nums[0]));
        System.out.println(missingNumber(nums[1]));

    }

    public static int missingNumber(int[] nums) {
        int length = nums.length;
        int check = (length * (length + 1)) / 2;
        for (int i = 0; i < length; i++) {
            check = check - nums[i];
        }
        return check;
    }

    public static void main6(String[] args) {
        int[][] num = {
                {1,2,4,5,3},
                {1,2,3},
                {1,5,1}
        };
        for (int[] ints : num) {
            nextPermutation1(ints);
            System.out.println(Arrays.toString(ints));
        }
    }

    public static void nextPermutation1(int[] nums) {
        int orderPointStart = -1;
        int orderPointEnd = -1;
        for (int i = 0; i < nums.length - 1; i++) {
            int check = 0;
            if (nums[i] > nums[i + 1] ) {
                check++;
                if (orderPointStart == -1){
                    orderPointStart = i;
                }
            }
            if (nums[i] < nums[i + 1] && orderPointStart != -1) {
                orderPointEnd = i - 1;
            }
            if (orderPointStart == 0 && check != 0 && i == nums.length - 2){
                orderPointEnd = i + 1;
            }
            if (orderPointStart == -1 && check == 0 && i == nums.length - 2){
                orderPointStart = 0;
                orderPointEnd = -1;
            }
        }
        if (orderPointStart == 0 && orderPointEnd != nums.length - 1){
            orderPointStart = nums.length - (orderPointEnd - orderPointStart + 1) - 1;
            orderPointEnd = nums.length - 1;
            int temp = nums[orderPointStart - 1];
            for (int i = orderPointStart - 1; i < orderPointEnd; i++) {
                nums[i] = nums[i + 1];
            }
            nums[orderPointEnd] = temp;
        }
        if (orderPointStart == 0 && orderPointEnd == nums.length - 1){
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < nums.length - i - 1; j++) {
                    if (1 * nums[j] > 1 * nums[j + 1]) {
                        int temp = nums[j];
                        nums[j] = nums[j + 1];
                        nums[j + 1] = temp;
                    }
                }
            }
        }
        if (orderPointStart > 0 && orderPointEnd < nums.length - 1){
            int temp = nums[orderPointStart - 1];
            for (int i = orderPointStart - 1; i < orderPointEnd; i++) {
                nums[i] = nums[i + 1];
            }
            nums[orderPointEnd] = temp;
        }
    }

    public static void main5(String[] args) {
        int[][] num = {
                {1, -7},//0
                {4,5,6,7,0,1,2},//1
                {14, 20, 27, 2, 5, 9},//2
                {17, 23, 31, 38, -9, -2, 4, 11},//3
                {22, 29, 35, 40, 47, 1, 6, 10, 15},//4
                {-88, -60, -45, -20, 3, 11, -95},//5
                {-2340, -2325, -2310, -2295, -2280, -2265, -2250, -2235, -2220, -2205, -2190, -2175, -2160, -2145, -2130, -2115, -2100, -2085, -2070, -2055, -2040, -2025, -2010, -1995, -1980, -1965, -1950, -1935, -1920, -1905, -1890, -1875, -1860, -1845, -1830, -1815, -1800, -1785, -1770, -1755, -1740, -1725, -1710, -1695, -1680, -1665, -1650, -1635, -1620, -1605, -1590, -1575, -1560, -1545, -1530, -1515, -1500, -1485, -1470, -1455, -1440, -1425, -1410, -1395, -1380, -1365, -1350, -1335, -1320, -1305, -1290, -1275, -1260, -1245, -1230, -1215, -1200, -1185, -1170, -1155, -1140, -1125, -1110, -1095, -1080, -1065, -1050, -1035, -1020, -1005, -990, -975, -960, -945, -930, -915, -900, -885, -870, -855, -840, -825, -810, -795, -780, -765, -750, -735, -720, -705, -690, -675, -660, -645, -630, -615, -600, -585, -570, -555, -540, -525, -510, -495, -480, -465, -450, -435, -420, -405, -390, -375, -360, -345, -330, -315, -300, -285, -270, -255, -240, -2595, -2580, -2565, -2550, -2535, -2520, -2505},//6
                {3240, 3255, 3270, 3285, 3300, 3315, 3330, 3345, 3360, 3375, 3390, 3405, 3420, 3435, 3450, 3465, 3480, 3495, 3510, 3525, 3540, 3555, 3570, 3585, 3600, 3615, 3630, 3645, 3660, 3675, 3690, 3705, 3720, 3735, 3750, 3765, 3780, 3795, 3810, 3825, 3840, 3855, 3870, 3885, 3900, 3915, 3930, 3945, 3960, 3975, 3990, 4005, 4020, 4035, 4050, 4065, 4080, 4095, 4110, 4125, 4140, 4155, 4170, 4185, 4200, 4215, 4230, 4245, 4260, 4275, 4290, 4305, 4320, 4335, 4350, 4365, 4380, 4395, 4410, 4425, 4440, 4455, 4470, 4485, 4500, 4515, 4530, 4545, 4560, 4575, 4590, 4605, 4620, 4635, 4650, 4665, 4680, 4695, 4710, 4725, 4740, 4755, 4770, 4785, 4800, 2800, 2815, 2830, 2845, 2860, 2875, 2890, 2905, 2920, 2935, 2950, 2965, 2980, 2995, 3010, 3025, 3040, 3055, 3070, 3085, 3100, 3115, 3130, 3145, 3160, 3175, 3190, 3205, 3220, 1800, 1815, 1830, 1845, 1860, 1875, 1890, 1905, 1920, 1935, 1950, 1965, 1980, 1995, 2010, 2025, 2040, 2055, 2070, 2085, 2100, 2115, 2130, 2145, 2160, 2175, 2190, 2205, 2220, 2235, 2250, 2265, 2280, 2295, 2310, 2325, 2340, 2355, 2370, 2385, 2400, 2415, 2430, 2445, 2460, 2475, 2490, 2505, 2520, 2535, 2550, 2565, 2580, 2595, 2610, 2625, 2640, 2655, 2670, 2685, 2700, 2715, 2730, 2745, 2760, 2775, 2790},//7
                {-8760, -8742, -8724, -8706, -8688, -8670, -8652, -8634, -8616, -8598, -8580, -8562, -8544, -8526, -8508, -8490, -8472, -8454, -8436, -8418, -8400, -8382, -8364, -8346, -8328, -8310, -8292, -8274, -8256, -8238, -8220, -8202, -8184, -8166, -8148, -8130, -8112, -8094, -8076, -8058, -8040, -8022, -8004, -7986, -7968, -7950, -7932, -7914, -7896, -7878, -7860, -7842, -7824, -7806, -7788, -7770, -7752, -7734, -7716, -7698, -7680, -7662, -7644, -7626, -7608, -7590, -7572, -7554, -7536, -7518, -7500, -7482, -7464, -7446, -7428, -7410, -7392, -7374, -7356, -7338, -7320, -7302, -7284, -7266, -7248, -7230, -7212, -7194, -7176, -7158, -7140, -7122, -7104, -7086, -7068, -7050, -7032, -7014, -6996, -6978, -6960, -6942, -6924, -6906, -6888, -6870, -9200, -9182, -9164, -9146, -9128, -9110, -9092, -9074, -9056, -9038, -9020, -9002, -8984, -8966, -8948, -8930, -8912, -8894, -8876, -8858, -8840, -8822, -8804, -8786, -8768, -8750, -8732, -8714, -8696, -8678, -8660, -8642, -8624, -8606, -8588, -8570, -8552, -8534, -8516, -8498, -8480, -8462, -8444, -8426, -8408, -8390, -8372, -8354, -8336, -8318, -8300, -8282, -8264, -8246, -8228, -8210, -8192, -8174, -8156, -8138, -8120, -8102, -8084, -8066, -8048, -8030, -8012, -7994, -7976, -7958, -7940, -7922, -7904, -7886, -7868, -7850, -7832, -7814, -7796, -7778, -7760, -7742, -7724, -7706, -7688, -7670, -7652, -7634, -7616, -7598, -7580, -7562, -7544, -7526, -7508, -7490, -7472, -7454, -7436, -7418, -7400},//8
                {6890, 6905, 6920, 6935, 6950, 6965, 6980, 6995, 7010, 7025, 7040, 7055, 7070, 7085, 7100, 7115, 7130, 7145, 7160, 7175, 7190, 7205, 7220, 7235, 7250, 7265, 7280, 7295, 7310, 7325, 7340, 7355, 7370, 7385, 7400, 7415, 7430, 7445, 7460, 7475, 7490, 7505, 7520, 7535, 7550, 7565, 7580, 7595, 7610, 7625, 7640, 7655, 7670, 7685, 7700, 7715, 7730, 7745, 7760, 7775, 7790, 7805, 7820, 7835, 7850, 7865, 7880, 7895, 7910, 7925, 7940, 7955, 7970, 7985, 8000, 5200, 5215, 5230, 5245, 5260, 5275, 5290, 5305, 5320, 5335, 5350, 5365, 5380, 5395, 5410, 5425, 5440, 5455, 5470, 5485, 5500, 5515, 5530, 5545, 5560, 5575, 5590, 5605, 5620, 5635, 5650, 5665, 5680, 5695, 5710, 5725, 5740, 5755, 5770, 5785, 5800, 5815, 5830, 5845, 5860, 5875, 5890, 5905, 5920, 5935, 5950, 5965, 5980, 5995, 6010, 6025, 6040, 6055, 6070, 6085, 6100, 6115, 6130, 6145, 6160, 6175, 6190, 6205, 6220, 6235, 6250, 6265, 6280, 6295, 6310, 6325, 6340, 6355, 6370, 6385, 6400, 6415, 6430, 6445, 6460, 6475, 6490, 6505, 6520, 6535, 6550, 6565, 6580, 6595, 6610, 6625, 6640, 6655, 6670, 6685, 6700}//9
        };
        System.out.println(search(num[1],0));
    }

    public static int search(int[] nums, int target) {
        for(int i = 0, j = nums.length - 1; i <= j;){
            int mid = (i + j) / 2;
            if(nums[mid] == target){
                return mid;
            }
            if (target > nums[0]){
                j = mid - 1;
            } else if (target < nums[nums.length - 1]) {
                i = mid + 1;
            } else {
                if (target == nums[0]){
                    return 0;
                }
                if (target == nums[nums.length - 1]){
                    return nums.length - 1;
                }
            }
        }
        return -1;
    }

    public static void main4(String[] args) {
        int[] num = {1,1,5};
        nextPermutation0(num);
        System.out.println(Arrays.toString(num));
    }

    public static void nextPermutation0(int[] nums) {
        if (nums.length == 1){
            return;
        }else if (nums.length == 2){
            int temp = nums[0];
            nums[0] = nums[1];
            nums[1] = temp;
            return;
        }
        int[] num = new int[]{1,1,5};
        boolean check = nums.equals(num);
        System.out.println(check);
    }

    public static void main3(String[] args) {
        int[] nums = {0,1,2,2,3,0,4,2}; // 输入数组
        int val = 2; // 要移除的值
        // 它以不等于 val 的值排序。
        int k = removeElement(nums, val); // 调用你的实现
        System.out.println(Arrays.toString(nums));
        System.out.println(k);
    }

    public static int removeElement(int[] nums, int val) {
        int ret = 0;
        int check = 0;
        boolean ccheck = false;
        for (int i = 0, p = 0; i < nums.length; i++) {
            if (nums[i] != val){
                nums[p] = nums[i];
                p++;
                ret++;
            }
        }
        return ret;
    }

    public static void main2(String[] args) {
        int[] nums = {0,0,1,1,1,2,2,3,3,4}; // 输入数组
        int k = removeDuplicates(nums);
        System.out.println(Arrays.toString(nums));
        System.out.println(k);
    }

    public static int removeDuplicates(int[] nums) {
        int ret = 1;
        int p = 0;
        for(int i = 0, j = 1; i < nums.length; i++){
            if(nums[i] != nums[p]){
                p++;
                nums[p] = nums[i];
                ret++;
            }
        }
        return ret;
    }

    public static void main1(String[] args) {
        String[] str = {"cir","car"};
        System.out.println(longestCommonPrefix(str));
    }

    public static String longestCommonPrefix(String[] strs) {
        String ret = new String();
        int minLength = strs[0].length();
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].length() < minLength){
                minLength = strs[i].length();
            }
        }
        for (int i = 0; i < minLength; i++) {
            boolean check = true;
            char firstCh = strs[0].charAt(i);
            for (int j = 0; j < strs.length; j++) {
                if (strs[j].charAt(i) != firstCh){
                    check = false;
                    break;
                }
            }
            if (check == true){
                ret += firstCh;
            }else {
                return ret;
            }

        }
        return ret;
    }

    public static int maxArea(int[] height) {
        int p1 = 0;
        int p2 = height.length - 1;
        for(int i = 0, j = height.length - 1; i < j; i++, j--){
            int area = height[p1] < height[p2] ? height[p1] * (p2 - p1) : height[p2] * (p2 - p1);
            int area_i = height[i] < height[p2] ? height[i] * (p2 - i) : height[p2] * (p2 - i);
            int area_j = height[p1] < height[j] ? height[p1] * (j - p1) : height[j] * (j - p1);
            area_i = area_i > 0 ? area_i : -area_i;
            area_j = area_j > 0 ? area_j : -area_j;
            if (area_i > area){
                if (height[p1] < height[p2]){
                    p1 = i;
                }else{
                    p2 = i;
                }
            }
            if (area_j > area){
                if(height[p1] > height[p2]){
                    p2 = j;
                }else{
                    p1 = j;
                }
            }
        }
        return height[p1] < height[p2] ? height[p1] * (p2 - p1) : height[p2] * (p2 - p1);
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] nums3 = new int[m + n];
        for (int i = 0; i < m; i++) {
            nums3[i] = nums1[i];
        }
        for (int i = 0; i < n; i++) {
            nums3[i + m] = nums2[i];
        }
        sort(nums3, 1);
        double ret = 0.0;
        if ((m + n) % 2 == 1) {
            ret = (double) nums3[(m + n) / 2];
        } else {
            int mn = (m + n) / 2;
            int ch_1 = nums3[mn];
            int ch_2 = nums3[mn - 1];
            ret = ((double) (ch_1 + ch_2)) / 2.0;
        }
        return ret;
    }

    public static void sort(int[] num, int FAR) {
        for (int i = 0; i < num.length; i++) {
            for (int j = 0; j < num.length - i - 1; j++) {
                if (FAR * num[j] > FAR * num[j + 1]) {
                    int temp = num[j];
                    num[j] = num[j + 1];
                    num[j + 1] = temp;
                }
            }
        }
    }

    public static void sort(int[] num, int FAR, int start, int end) {
        for (int i = start; i < end; i++) {
            for (int j = start; j < end - i - 1; j++) {
                if (FAR * num[j] > FAR * num[j + 1]) {
                    int temp = num[j];
                    num[j] = num[j + 1];
                    num[j + 1] = temp;
                }
            }
        }
    }

    public static void main0(String[] args) {
//        int[] num1 = {1, 3};
//        int[] num2 = {2};
//        System.out.println(findMedianSortedArrays(num1, num2));
//        int[] num = {1,8,6,2,5,4,8,3,7};
        int[] num = {8,7,2,1};
        System.out.println(maxArea(num));
    }
}